package __贪心算法

/*
https://leetcode.cn/problems/partition-labels/description/

763.划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：
输入：s = "eccbbbbdec"
输出：[10]
*/
func partitionLabels(s string) []int {
	var res []int     //结果数组
	var marks [26]int //该字符在字符串中最远的出现位置

	size, left, right := len(s), 0, 0
	for i := 0; i < size; i++ { //统计每个字符在字符串中，最远出现的位置
		marks[s[i]-'a'] = i
	}

	for i := 0; i < size; i++ {
		right = max(right, marks[s[i]-'a']) //更新right的最远位置
		if i == right {                     //如果i已经走到了本范围字符串的最远位置right处, 进行分割
			res = append(res, right-left+1)
			left = i + 1
		}
	}
	return res
}
